package algorithm.leetcode.medium;

/*
 给定不同面额的硬币 coins 和一个总金额 amount。
 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 如果没有任何一种硬币组合能组成总金额，返回 -1。
 你可以认为每种硬币的数量是无限的。
 */

import java.util.Arrays;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/30
 */
public class Question322 {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        Question322 question = new Question322();
        int change = question.coinChange(coins, 11);
        System.out.println(change);
    }


    /**
     * 思想：
     * 贪心算法 + 剪枝
     */
    int res = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if (amount == 0 || coins == null) {
            return 0;
        }
        Arrays.sort(coins);
        // 这里第三个参数取最后索引 体现出贪心
        helper(coins, amount, coins.length - 1, 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private void helper(int[] coins, int amount, int len, int count) {
        if (amount == 0) {
            res = Math.min(res, count);
            return;
        }
        if (len < 0) {
            return;
        }
        for (int i = amount / coins[len]; i >= 0 && i + count <= res; i--) {
            // 这里第二个参数 体现 剪枝
            helper(coins, amount - (i * coins[len]), len - 1, count + i);
        }
    }
}
